//
// Created by dengspc on 2019/2/14.
//

#ifndef INC_010_ALGORITHM_UF_H
#define INC_010_ALGORITHM_UF_H

#include <iostream>

using namespace std;

class UF{
protected:
    int counts;
    int* ids;
    int* szs;
    int size;
public:
    UF(int count = 0){
        this->counts = count;
        this->size = count;
        ids = new int[count];
        szs = new int[count];
        for (int i = 0; i < count; ++i) {
            ids[i] = i;
            szs[i] = 1;
        }
    }

    ~UF(){
        delete[] ids;
        delete[] szs;
    }
    virtual void unioned(int p, int q) = 0;//连接p,q
    virtual int find(int p) = 0; // p所在分量标识符
    bool connected(int p, int q) {
        return find(p) == find(q);
    } //p和q 存在同一个分量中则返回true
    int count() {
        return counts;
    }//联通分量数量
};

/**
 * 集合为一个链表的形式
 */
class UFimp1:public UF{
public:
    UFimp1(int count = 0):UF(count){}

    void unioned(int p, int q){
        if(!connected(p,q)) {
            ids[find(p)] = q;
            counts--;
        }
    }//连接p,q
    int find(int p) {
        int n = p;
        while(ids[n] != n){
            n = ids[n];
        }
        return n;
    } // p所在分量标识符
};

/**
 * 集合为一层树的形式 find quick
 */
class UFimp2:public UF{
public:
    UFimp2(int count = 0):UF(count){}

    void unioned(int p, int q){
        int pID = find(p);
        int qID = find(q);

        if(pID == qID) return ;
        for (int i = 0; i < size; ++i) {
            if(ids[i] == pID)
                ids[i] = qID;
        }
        counts--;
    }//连接p,q
    int find(int p) {
        return ids[p];
    } // p所在分量标识符
};


/**
 * 根结合的的方式合并 union quick
 */
class UFimp3:public UF{
public:
    UFimp3(int count = 0):UF(count){}

    void unioned(int p, int q){
        int pID = find(p);
        int qID = find(q);

        if(pID == qID) return ;

        ids[pID] = qID;

        counts--;
    }//连接p,q
    int find(int p) {
        while(p!=ids[p]) p=ids[p];
        return p;
    } // p所在分量标识符
};


/**
 * 根结合的的方式合并 加权union quick
 */
class UFimp4:public UF{
public:
    UFimp4(int count = 0):UF(count){}

    void unioned(int p, int q){
        int pID = find(p);
        int qID = find(q);

        if(pID == qID) return ;

        if(szs[pID] > szs[qID] ){
            ids[qID] = pID;
            szs[pID]+=szs[qID];
        }else{
            ids[pID] = qID;
            szs[qID]+=szs[pID];
        }
        counts--;
    }//连接p,q
    int find(int p) {
        while(p!=ids[p]) p=ids[p];
        return p;
    } // p所在分量标识符
};

/**
 * 根结合的的方式合并 加权union quick
 */
class UFimp5:public UF{
public:
    UFimp5(int count = 0):UF(count){}

    void unioned(int p, int q){
        int pID = find(p);
        int qID = find(q);

        if(pID == qID) return ;

        if(szs[pID] > szs[qID] ){
            ids[qID] = pID;
        }else if(szs[pID] < szs[qID] ){
            ids[pID] = qID;
        }else{
            ids[pID] = qID;
            szs[qID]++;
        }
        counts--;
    }//连接p,q
    int find(int p) {
        while(p!=ids[p]) p=ids[p];
        return p;
    } // p所在分量标识符
};

#endif //INC_010_ALGORITHM_UF_H
